package com.algorithm;

/**
 * 寻找数组中的最小元素的索引, 将未排序部分的最小元换到有序部分的末尾
 * Created by houjinxin on 16/5/9.
 */
public class SelectionSort {

    public static void selectionSort(int[] arr) {
        //将整个数组进行非递减排序
        for (int i = 0; i < arr.length; i++) {
            //寻找数组中的最小元并返回索引
            int minIndex = scanMin(arr, i, arr.length - 1);
//            System.out.println(minIndex);
            //将未排序部分最小元换到有序部分的末尾
            swap(arr, i, minIndex);
        }
    }

    public static int scanMin(int[] arr, int from, int to) {
        int minIndex = from;
        int min = arr[from];
        for (int i = from; i <= to; i++) {
            if (arr[i] < min) {
                min = arr[i];
                minIndex = i;
            }
        }
        return minIndex;
    }

    public static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }


    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 10, 6, 7, 8, 9};
        selectionSort(arr);
        for (int a : arr) {
            System.out.println(a);
        }
    }
}
